翻訳と辞書
Words near each other
・ Succieu
・ Succimorda
・ Succinaldehyde
・ Succinate dehydrogenase
・ Succinate dehydrogenase complex subunit C
・ Succinate dehydrogenase subunit E
・ Succinate-semialdehyde dehydrogenase
・ Succinate-semialdehyde dehydrogenase (acylating)
・ Succinate-semialdehyde dehydrogenase (NAD(P)+)
・ Succinate-semialdehyde dehydrogenase (NADP+)
・ Succinate—citramalate CoA-transferase
・ Succinate—CoA ligase (ADP-forming)
・ Succinate—CoA ligase (GDP-forming)
・ Succinate—hydroxymethylglutarate CoA-transferase
・ Succinct (disambiguation)
Succinct data structure
・ Succinct game
・ Succinctness
・ Succinea
・ Succinea antiqua
・ Succinea approximans
・ Succinea archeyi
・ Succinea costaricana
・ Succinea forsheyi
・ Succinea guamensis
・ Succinea philippinica
・ Succinea piratarum
・ Succinea putris
・ Succinea quadrasi
・ Succinea sanctaehelenae


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

Succinct data structure : ウィキペディア英語版
Succinct data structure
In computer science, a succinct data structure is a data structure which uses an amount of space that is "close" to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations. The concept was originally introduced by Jacobson〔 to encode bit vectors, (unlabeled) trees, and planar graphs. Unlike general lossless data compression algorithms, succinct data structures retain the ability to use them in-place, without decompressing them first. A related notion is that of a compressed data structure, in which the size of the data structure depends upon the particular data being represented.
Suppose that Z is the information-theoretical optimal number of bits needed to store some data. A representation of this data is called:
* ''implicit'' if it takes Z + O(1) bits of space,
* ''succinct'' if it takes Z + o(Z) bits of space, and
* ''compact'' if it takes O(Z) bits of space.
For example, a data structure that uses 2Z bits of storage is compact, Z + \sqrt bits is succinct, Z + \lg Z bits is also succinct, and Z + 3 bits is implicit.
Implicit structures are thus usually reduced to storing information using some permutation of the input data; the most well-known example of this is the heap.
==Succinct dictionaries==
Succinct indexable dictionaries, also called ''rank/select'' dictionaries, form the basis of a number of succinct representation techniques, including binary trees, k-ary trees and multisets,〔 as well as suffix trees and arrays.〔 The basic problem is to store a subset S of a universe U =
: B() = q \}|
* \mathbf_q(x)= \min \ \lg n \lg \lg n) = o(n) bits of additional storage can be used to support select in constant time.〔 In practice, many of these solutions have hidden constants in the O(\cdot) notation which dominate before any asymptotic advantage becomes apparent; implementations using broadword operations and word-aligned blocks often perform better in practice.〔

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「Succinct data structure」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.